package zcw.com.lib_leet_code;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/26.<br><br>
 *
 * 二叉树的右视图
 */
public class Topic199 {

    public static void main(String[] args) {
        Topic199 instance = new Topic199();

        List<Integer> list = Arrays.asList(1,2,3,null,5,null,4);
        TreeNode root = Util.createTree(list);
        System.out.println(instance.rightSideView(root));

        list = Arrays.asList(1,null,3);
        root = Util.createTree(list);
        System.out.println(instance.rightSideView(root));

        list = Collections.emptyList();
        root = Util.createTree(list);
        System.out.println(instance.rightSideView(root));
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }

        helper(root, 0, list);
        return list;
    }

    private void helper(TreeNode root, int deep, List<Integer> result) {
        if(root == null) {
            return ;
        }

        if(deep == result.size()) {
            result.add(root.val);
        }

        helper(root.right, deep + 1, result);
        helper(root.left, deep + 1, result);
    }

    public List<Integer> rightSideView3(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }

        TreeNode endNode = new TreeNode(101);
        Queue<TreeNode> stack = new ArrayDeque<>();
        stack.offer(root);
        stack.offer(endNode);

        TreeNode prev = null;
        while (!stack.isEmpty()) {
            TreeNode node = stack.poll();
            if(node.val == 101 && prev != null) {
                list.add(prev.val);
                stack.offer(endNode);
                prev = null;
                continue;
            }

            prev = node;
            if(node.left != null) {
                stack.offer(node.left);
            }

            if(node.right != null) {
                stack.offer(node.right);
            }
        }

        return list;
    }

    public List<Integer> rightSideView2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }

        Queue<TreeNode> stack = new ArrayDeque<>();
        Queue<TreeNode> stackReverse = new ArrayDeque<>();
        stack.offer(root);

        while (!stack.isEmpty() || !stackReverse.isEmpty()) {
            while (!stack.isEmpty()) {
                TreeNode node = stack.poll();
                if(stack.isEmpty()) {
                    list.add(node.val);
                }

                if(node.left != null) {
                    stackReverse.offer(node.left);
                }

                if(node.right != null) {
                    stackReverse.offer(node.right);
                }
            }

            while (!stackReverse.isEmpty()) {
                TreeNode node = stackReverse.poll();
                if(stackReverse.isEmpty()) {
                    list.add(node.val);
                }

                if(node.left != null) {
                    stack.offer(node.left);
                }

                if(node.right != null) {
                    stack.offer(node.right);
                }
            }
        }

        return list;
    }
}
